#include <iostream>
#include <ctime>
using namespace std;
const int  maxsize=100;
int n;
int a[maxsize];
int b[maxsize];
void print()
{
    for (int j = 0; j < n; ++j) {
         cout<<a[j]<<" ";
    }
    cout<<endl;
}
void Reverse(int left,int right)
{
    int i=left,j=right;
    for(int i=left,j=right;i<=j;i++,j--)
        swap(a[i],a[j]);
}
void ArrayRightMove(int a[],int left,int mid,int right)
{

    int i=left,j=mid+1;
    while(i<=mid&&j<=right)
    {
        while(a[i]<=a[j]&&i<=mid)
        {
            i++;
        }
        //此时退出循环a[i]比a[j]大
        int index=j;
        while(a[j]<a[i]&&j<=right)
        {
            j++;
        }
        //此时的(index,j-1)都比 a[i]小所以要左旋到最左边
        Reverse(index,j-1);
        Reverse(i,index-1);
        Reverse(i,j-1);
        i=i+(j-1-index+1);//有几个过来了就向右移动几个
        mid=j-1;

    }

}

void MergeSort(int a[],int left,int right)
{
    if(left>=right)
        return;
    //待带排序序列分成2部分
    //不断的分知道遇到递归边界分成一个数了然后开始合并
     int mid=(left+right)/2;
     MergeSort(a,left,mid);
     MergeSort(a,mid+1,right);
     //O(n)的算法 合并两个数组中
     //合并 (left,mid)以及(mid+1,left)
     //浪费一个临时的空间b[]来进行合并;
     //递归的返回的时候保证子序列已经是有序的了
     //由于使用了临时的数组空间空间复杂度很浪费索引考虑原地归并


     /*
      * 手摇算法原地归并
      */
     ArrayRightMove(a,left,mid,right);

//     int k=0;
//     int i=left;
//     int j=mid+1;
//     while(i<=mid&&j<=right)
//     {
//         if(a[i]<=a[j])
//         {
//             b[k++]=a[i++];
//         }
//         else
//         {
//             b[k++]=a[j++];
//         }
//     }
//     while (i<=mid)
//     {
//         b[k++]=a[i++];
//     }
//     while (j<=right)
//     {
//         b[k++]=a[j++];
//     }
//     //此时b数组以及有序 元素位置从 0-k-1
//     //将0-k-1的元素全部挪到a中
//     for(int i=0;i<k;i++)
//     {
//         a[left+i]=b[i];
//     }

}
int main() {
    cin>>n;
    srand(time(0));
    for (int i = 0; i <n ; ++i) {
        a[i]=rand()%100;
    }
    //排序前
    print();
    MergeSort(a,0,n-1);
    //排序后
    print();

    return 0;
}
